class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        求数组组成的容器能接多少水，leetcode-042
        解题思路，第一步将所有峰值求出来为一个数组，第二步将数组转成中间大两边递减的数组，两边小的数组，第三步求盛的水量
        """
        if len(height) < 3:
            return 0
        # 第一步求所有峰值
        i, key1, val1 = 0, [], []
        while i < len(height):
            if i == 0 and height[i+1] <= height[i]:
                key1.append(i)
                val1.append(height[i])
                i += 1
            elif i == len(height) - 1 and height[i-1] < height[i]:
                key1.append(i)
                val1.append(height[i])
                i += 1
            elif height[i-1] < height[i] and height[i] >= height[i+1]:
                key1.append(i)
                val1.append(height[i])
                i += 1
            else:
                i += 1
        print(key1)
        print(val1)
        # 第二步求所有符合要求的峰值
        if len(val1) < 2:
            return 0
        i = 0
        val1_max = max(val1)
        key2, key3 = [key1[0]], [key1[len(val1)-1]]
        max1 = val1[0]
        max2 = val1[len(val1)-1]
        while i < len(val1)-1:
            j = len(val1)-1-i
            if max1 <= val1[i+1] <= val1_max:
                print(111)
                key2.append(key1[i+1])
                max1 = val1[i+1]
            if max2 <= val1[j-1] <= val1_max:
                print(222)
                key3.append(key1[j-1])
                max2 = val1[j-1]
            i += 1

        key2.extend(key3)
        key2 = list(set(key2))
        key2.sort()
        print(key2)
        print(key3)

        # 第三步求最后的值
        if len(key2) < 2:
            return 0
        i = 0
        total = total2 = 0
        while i < len(key2)-1:
            # print(333)
            min_v = min([height[key2[i]], height[key2[i+1]]])
            total = (abs(key2[i] - key2[i+1])-1) * min_v
            middle = height[key2[i]+1:key2[i+1]]
            for x in middle:
                if x > min_v:
                    total = total - min_v
                else:
                    total = total - x
            total2 += total
            i += 1
        print(height)

        return total2


sol = Solution()
s = [1, 3, 7, 4, 9, 3, 9, 1, 4, 3, 6]
s1 = [0,1,0,2,1,0,1,3,2,1,2,1]
s2 = [5,4,1,2]
s3 = [2,0,2]
s4 = [5,5,1,7,1,1,5,2,7,6]
s5 = [6,2,2,9,6,8,5,8,3,7,3,8,9,8,1,2,4]
res = sol.trap(s3)
print(res)
